package HashTable;
import java.util.*;
//给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
//        字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
//        示例 1:
//        输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
//        输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

//        示例 2:
//        输入: strs = [""]
//        输出: [[""]]

//        示例 3:
//        输入: strs = ["a"]
//        输出: [["a"]]
public class lc49 {
    public static void main(String[] args) {
        String[] strs =new String[]{"eat","tea","tan","ate","nat","bat"};
        groupAnagrams(strs);

    }
    public static List<List<String>> groupAnagrams(String[] strs) {
        //这个方法时间复杂度大
        //利用一个小list设置一个hashset数组来减小时间复杂度
        List<List<String>> result=new ArrayList<>();
        if(strs.length==0){
            return result;
        } else if (strs.length==1) {
            List<String> list=new ArrayList<>();
            list.add(strs[0]);
            result.add(list);
            return result;
        }else {
            //设置一个数组判定某个元素是否以及参与构建List<String>
            boolean[] isadded =new boolean[strs.length];
            //第一个小list在循环外创建
            List<String> list1=new ArrayList<>();
            list1.add(strs[0]);
            int[] hashset0=new int[26];
            char[] chars0 = strs[0].toCharArray();
            for (int i = 0; i < chars0.length ; i++) {
                hashset0[chars0[i]-'a']++;
            }//对数组完成赋值
            for (int i = 1; i <strs.length ; i++) {
                int[] hashset_back0=new int[26];
                for (int j = 0; j < hashset0.length ; j++) {
                    hashset_back0[j]=hashset0[j];
                }//定义副本数组，让每次归零操作的对象是副本数组
                if(issame(list1.get(0),strs[i],hashset_back0)){
                    list1.add(strs[i]);
                    isadded[i]=true;
                }
            }
            result.add(list1);
            //从第二个字符串开始循环
            for (int i = 1; i <strs.length ; i++) {
                if(isadded[i]==false){//如果该元素还没被放入小list，则新建一个小list
                    List<String> list=new ArrayList<>();
                    list.add(strs[i]);
                    int[] hashset=new int[26];
                    char[] chars = strs[i].toCharArray();
                    for (int j = 0; j < chars.length ; j++) {
                        hashset[chars[j]-'a']++;
                    }
                    for (int j = i+1; j <strs.length ; j++) {
                        if(isadded[j]==true){
                            continue;
                        }
                        int[] hashset_back=new int[26];
                        for (int k = 0; k <26 ; k++) {
                            hashset_back[k]=hashset[k];
                        }
                        if(issame(list.get(0),strs[j],hashset)){
                            isadded[j]=true;
                            list.add(strs[j]);
                        }
                    }
                    result.add(list);
                }else {
                   continue;
                }
            }
        }
        return result;

    }

    public static boolean issame(String s,String t,int[] hashset){  //判断两个数组是否拥有一样的元素
        if(s.length()!=t.length()){
            return false;
        }
        char[] t_chars=t.toCharArray();
        for (char c:t_chars
        ) {
            hashset[c-'a']--;
        }
        for (int i = 0; i <hashset.length ; i++) {
            if(hashset[i]!=0) return false;
        }
        return  true;
    }


    public List<List<String>> groupAnagrams1(String[] strs) {

      /*  map.getOrDefault(key, new ArrayList<String>()) 方法的作用是：
        如果哈希表 map 中存在键 key，则返回与该键对应的值。
        如果哈希表 map 中不存在键 key，则返回一个默认值，这里是一个新创建的空的 ArrayList<String> 对象。*/
        // 创建一个映射表用于存储分组结果
        Map<String, List<String>> map = new HashMap<>();

        // 遍历输入的字符串数组
        for (String str : strs) {
            // 将当前字符串转换为字符数组并进行排序
            char[] array = str.toCharArray();
            Arrays.sort(array);

            // 将排序后的字符数组转换为字符串，并作为映射表的键
            String key = new String(array);

            // 获取当前键对应的分组列表，如果不存在则创建一个新的列表
            List<String> list = map.getOrDefault(key, new ArrayList<String>());

            // 将当前字符串添加到对应的分组列表中
            list.add(str);

            // 更新映射表中的键值对
            map.put(key, list);
        }

        // 返回映射表中的所有分组列表
        return new ArrayList<List<String>>(map.values());
    }
    public List<List<String>> groupAnagrams2(String[] strs) {
        HashMap<String,List<String>> map=new HashMap<>();

        for (String str:strs) {
            char[] chars=str.toCharArray();
            Arrays.sort(chars);
            String s = String.valueOf(chars);
            List<String> list = map.getOrDefault(s, new ArrayList<String>());
            list.add(str);
            map.put(s, list);
        }
        return new ArrayList<List<String>>(map.values());

    }
}
